package 每日一题;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-30
 **/

public class No260只出现一次的数字III {

    /**
     * 给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。
     * 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
     * <p>
     * 进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
     * <p>
     * 示例 1：
     * 输入：nums = [1,2,1,3,2,5]
     * 输出：[3,5]
     * 解释：[5, 3] 也是有效的答案。
     * 示例 2：
     * 输入：nums = [-1,0]
     * 输出：[-1,0]
     * 示例 3：
     * 输入：nums = [0,1]
     * 输出：[1,0]
     * <p>
     * 提示：
     * 2 <= nums.length <= 3 * 104
     * -231 <= nums[i] <= 231 - 1
     * 除两个只出现一次的整数外，nums 中的其他数字都出现两次
     */

    public int[] singleNumber(int[] nums) {

        /**
         * 全体异或后,随便取一位为1的位,然后以当前位将数组元素分为两组,后续对这两组元素分别进行全部异或,得出答案。
         */

        int n1 = 0;

        for (int num : nums) {
            n1 ^= num;
        }

        int n2 = 0;

        for (int i = 0; i < 32; i++) {
            if (((1 << i) & n1) != 0) {
                n2 = 1 << i;
                break;
            }
        }

        int n3 = 0;
        int n4 = 0;

        for (int num : nums) {
            if ((num & n2) == 0) {
                n3 ^= num;
            } else {
                n4 ^= num;
            }
        }

        return new int[]{n3, n4};
    }

}
